package demo.tree;

/**
 * 判断两个节点的最大距离
 */
public class MaxDistance {

    public static void main(String[] args) {
        Node node = TreeUtil.treeBuild();
        TreeUtil.treePrint(node);
        System.out.println(getMaxDistance(node));
    }

    public static int getMaxDistance(Node x) {
        return process(x).maxDistance;
    }

    public static Info process(Node x) {
        if (x == null) {
            return new Info(0, 0);
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int height = Math.max(leftInfo.height, leftInfo.height) + 1;
        int maxDistance = Math.max(Math.max(leftInfo.maxDistance, rightInfo.maxDistance), leftInfo.height + rightInfo.height + 1);

        return new Info(maxDistance, height);
    }

    private static class Info {
        public int maxDistance;
        public int height;

        public Info(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }
}
